// Time:  O(n)
// Space: O(1)

#include <vector>

using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        if(s.empty() || k < 0) {
            return 0;
        }

        vector<int> count(26, 0);
        int maxLen = 0, maxCount = 0;
        int left = 0;

        for(int right = 0; right < s.length(); ++right) {
            maxCount = max(maxCount, ++count[s[right] - 'A']);

            if((right - left + 1) - maxCount > k) {
                --count[s[left] - 'A'];
                ++left;
            }
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};
